package basis.netease.medium;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 7-8 分段反转链表
 * 给定一个常数 K 和一个单链表 L，请你在单链表上每 K 个元素做一次反转，并输出反转完成后的链表。
 * 如果链表最后一部分不足 K 个元素，则最后一部分不翻转。
 * 例如，假设 L 为 1→2→3→4→5→6
 * 如果 K=3，则你应该输出 3→2→1→6→5→4
 * 如果 K=4，则你应该输出 4→3→2→1→5→6
 * 输入格式:
 * 第一行包含头节点地址，总节点数量 N 以及常数 K。1≤N≤100000，1≤K≤N 。
 * 节点地址用一个 5 位非负整数表示（可能有前导 0），NULL 用 −1 表示。
 * 接下来 N 行，每行描述一个节点的信息，格式如下：
 * Address Data Next
 * 其中 Address 是节点地址，Data 是一个绝对值不超过100000的整数，Next 是下一个节点的地址。
 * 输出格式:
 * 将重新排好序的链表，从头节点开始，依次输出每个节点的信息，格式与输入相同。
 * 输入样例:
 * 在这里给出一组输入。例如：
 * 00100 6 4
 * 00000 4 99999
 * 00100 1 12309
 * 68237 6 -1
 * 33218 3 00000
 * 99999 5 68237
 * 12309 2 33218
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * 00000 4 33218
 * 33218 3 12309
 * 12309 2 00100
 * 00100 1 99999
 * 99999 5 68237
 * 68237 6 -1
 */
public class Main_8 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] title = in.nextLine().split(" ");
        String headAddress = title[0];
        int listSize = Integer.parseInt(title[1]);
        Integer reverseSize = Integer.valueOf(title[2]);
        // 构建链表映射关系
        Map<String, Node> nodeMap = new HashMap<>();
        for (int i = 0; i < listSize; i++) {
            String[] input = in.nextLine().split(" ");
            nodeMap.put(input[0], new Node(input[0], input[1], input[2]));
        }
        // 获取头节点，从头节点开始反转
        Node finalHeadNode = nodeMap.get(headAddress);
        Node currentNode = finalHeadNode;
        // 上一次处理的最后一个节点
        Node lastEndNode = currentNode;
        int reverseCount = listSize / reverseSize;
        for (int i = 0; i < reverseCount; i++) {
            Node firstNode = reverse(nodeMap, currentNode, reverseSize);
            if (i == 0) {
                // 获取链表最终的头节点
                finalHeadNode = firstNode;
            } else {
                // 上一次处理的最后一个节点的next指向这一次处理的第一个节点的地址
                lastEndNode.next = firstNode.address;
            }
            // 这一次处理的最后一个节点记录下来
            lastEndNode = currentNode;
            // 下一次要处理的开始节点即为上一次处理开始节点的next（因为上一个开始节点处理后已经变为了最后一个节点）
            currentNode = nodeMap.get(currentNode.next);
        }
        while (finalHeadNode != null) {
            System.out.println(finalHeadNode);
            finalHeadNode = nodeMap.get(finalHeadNode.next);
        }
    }

    public static Node reverse(Map<String, Node> nodeMap, Node startNode, Integer reverseSize) {
        // 双指针，记录当前处理的节点以及当前的下一个节点
        Node currentNode = startNode;
        Node nextNode = nodeMap.get(currentNode.next);
        for (int i = 0; i < reverseSize - 1; i++) {
            // 提前记住下一个处理的节点
            String nextAddress = nextNode.next;
            // 改变指向
            nextNode.next = currentNode.address;
            // 移动指针
            currentNode = nextNode;
            nextNode = nodeMap.get(nextAddress);
        }
        // 原来最开始第一个节点变成了最后一个节点
        startNode.next = nextNode == null ? "-1" : nextNode.address;
        // 返回的是反转后的头节点
        return currentNode;
    }

    public static class Node {
        public String address;
        public String data;
        public String next;

        public Node(String address, String data, String next) {
            this.address = address;
            this.data = data;
            this.next = next;
        }

        public String toString() {
            return address + " " + data + " " + next;
        }
    }

}
